package wheel.arithmetic;

import cn.hutool.core.util.ArrayUtil;
import cn.hutool.core.util.RandomUtil;

/**
 * 交换排序-快速排序
 *
 *
 * 选一个基准数，头尾两个Index设作两个游标，（以从小到大排序以例）
 * 小于基准的放在左边，大于基准的放在右边，
 * 头尾两个游标分别寻找，左边比基准大的数和右边比基准小的数。
 * 两个都找到了进行交换，直到两个游标指向同一index。
 */
public class QuickSort {

    public static void main(String[] args) {

        Integer[] arr = new Integer[100000000];
        for(int i=0; i<arr.length; i++){
            arr[i] = RandomUtil.randomInt(0, arr.length*100);
        }

//        arr = new Integer[]{245, 278, 473, 500, 627, 282, 763, 726, 1142, 761, 1189, 1242, 1322, 1458, 1355};
//        arr = new Integer[]{70, 837, 941, 1260, 300, 893, 467, 931, 1199, 1377, 370, 117, 660, 861, 533};
//        arr = new Integer[]{1276, 777, 20, 646, 1410, 691, 710, 285, 562, 1314, 333, 695, 1401, 1451, 811};


//        System.out.println("输入: "+ ArrayUtil.toString(arr));


        long startTime = System.currentTimeMillis();
//        arr = execute(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("耗时: "+(endTime-startTime)+"ms");
//        System.out.println("输出: "+ ArrayUtil.toString(arr));

        verifyDataCorrect(arr);

    }


    private static void verifyDataCorrect(Integer[] arr){
        Integer upValue = null;
        for(int i=0; i<arr.length; i++){
            int currValue = arr[i];
            if(upValue==null){
                upValue =currValue;
                continue;
            }
            if(upValue > currValue)
                throw new RuntimeException("算法输出结果不正确！！  数据下标: "+(i-1));
            upValue = currValue;
        }
        System.out.println("算法输出结果校验通过！！");
    }

    public static Long[] execute(Long[] arr){

        execute(arr, 0, arr.length-1);
        return arr;
    }

    private static void execute(Long[] arr, int startIndex, int endIndex) {
        int len = endIndex - startIndex + 1;

        if(len>5){
            Long dividePoint = arr[startIndex];
            int leftIndex = startIndex, rightIndex = endIndex + 1;
            Integer leftHitIndex = null, rightHitIndex = null;


            while(true){
                /**
                 * 寻找左边大于等于基准数的数
                 */
                while (leftHitIndex == null && leftIndex + 1 < rightIndex) {
                    leftIndex++;
                    if (arr[leftIndex] >= dividePoint)
                        leftHitIndex = leftIndex;

                }

                /**
                 * 寻找右边小于基准数的数
                 */
                while (rightHitIndex == null && rightIndex - 1 > leftIndex) {
                    rightIndex--;
                    if (arr[rightIndex] < dividePoint){
                        rightHitIndex = rightIndex;
                    }
                }

                /**
                 * 当左右都找到数时，进行交换
                 */
                if(rightHitIndex!=null && leftHitIndex!=null){
                    Long rightHitValue = arr[leftHitIndex];
                    arr[leftHitIndex] = arr[rightHitIndex];
                    arr[rightHitIndex] = rightHitValue;
                    leftHitIndex = null; rightHitIndex = null;
                }

                /**
                 * 收尾，把基准数放在左右边交界处
                 * 最后有三种情况
                 *  1）左右hit都有
                 *  2）左右hit只有一个有（这份实现中左先行，所以只有一个有的这种情况，都是左有)
                 *  3) 左右hit都没有
                 */
                if(leftIndex + 1 == rightIndex){
                    if(leftHitIndex!=null){
                        leftIndex--;
                        rightIndex--;
                    }
                    arr[startIndex] = arr[leftIndex];
                    arr[leftIndex] = dividePoint;
//                    System.out.println("快速排序过程: "+ArrayUtil.toString(arr)+", startIndex: "+startIndex+", endIndex: "+endIndex+", 基准数: "+dividePoint);
                    execute(arr, startIndex, leftIndex);
                    execute(arr, rightIndex, endIndex);
                    break;
                }
            }


        }else{
            //过小的数组直接使用简单选择排序
            SimpleSelectSort.exeucte(arr, startIndex, endIndex);

        }



    }


    //耗时: 7ms 9ms 7ms 一万个
    //耗时: 143ms 131ms 90ms 94ms 十万个
    //耗时: 574ms 538ms 530ms 一百万个
    //耗时: 6164ms 5473ms 一千万个
    //耗时: 146464ms 一亿个
}
